package oj;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 郝文雪
 * @date 2022/9/10 15:34
 * @Description Test
 */
public class LC947 {
    public int removeStones(int[][] stones) {
        UnionFind uf=new UnionFind();
        for(int[] stone : stones){
            uf.union(stone[0]+10001,stone[1]);
        }
        return stones.length-uf.getCount();
    }
}
//并查集
class UnionFind{
    private int count;
    Map<Integer,Integer> parent;
    public UnionFind(){
        this.count=0;
        this.parent=new HashMap<>();
    }
    //返回连通分量的个数
    public int getCount(){
        return count;
    }
    //返回某个节点x的根节点
    public int find(int x){
        if(!parent.containsKey(x)){
            count++;
            parent.put(x,x);
        }
        if(x!=parent.get(x)){
            parent.put(x,find(parent.get(x)));
        }
        return parent.get(x);
    }
    //将两个点进行连接
    public void union(int x,int y){
        int rootX=find(x);
        int rootY=find(y);
        if(rootX==rootY){
            return;
        }
        parent.put(rootX,rootY);
        count--;
    }
}